package two.chapter_5.c5_1;


import edu.princeton.cs.algs4.StdOut;

/**
 * 键索引排序方法，对于键为小整数的应用适用
 */
public class KeyIndexSort  {


    public void sort(Key[] keys,int R) {
        int N=keys.length;

        Key[]aux=new Key[N];

        int[] count=new int[N+1];
        //统计频率
        for (int i=0;i<N;i++){
            count[keys[i].key()+1]++;
        }

        //频率转索引
        for (int r = 0; r < R; r++) {
            count[r+1]+=count[r];
        }

        //排序
        for (int i = 0; i < N; i++) {
            aux[count[keys[i].key()]++]=keys[i];
        }
        //回写
        for (int i = 0; i < N; i++) {
            keys[i]=aux[i];
        }
    }

    private static class Key{
        private int key;
        public Key(int key){
            this.key=key;
        }
        private int key(){
            return key;
        }
    }
    public static void main(String []args){
        int N=10;
        Key[]keys=new Key[N];
        for (int i=0;i<N;i++){
            keys[i]=new Key(i);
        }
        KeyIndexSort sort=new KeyIndexSort();
        sort.sort(keys,N);

        for (int i = 0; i <N; i++) {
            StdOut.print(keys[i].key()+" ");
        }
    }
}
